摘要 :
Efficient task scheduling is required to attain high performance in both homogeneous and heterogeneous computing systems. An application can be considered as a task grid represented using a Directed Acyclic Graph (DAG). Solving su...
展开
Efficient task scheduling is required to attain high performance in both homogeneous and heterogeneous computing systems. An application can be considered as a task grid represented using a Directed Acyclic Graph (DAG). Solving such DAG representing a scheduling problem is an NP-complete task. The primary concern in this problem domain is to reduce the schedule length with minimum complexity. This work presents a Hybrid List-based Task Scheduling using Duplication Scheme (HLTSD) algorithm for heterogeneous processors. The proposed HLTSD algorithm has the same time complexity as that of the recent state-of-the-art algorithms. However, it produces a minimum cost schedule in comparison with other related methods. This work also presents a mathematical formulation to find task priorities. The processor selection phase is improved by utilizing the techniques, like entry task duplication, insertion-based policy, duplication of parent task on other levels, and balancing the load on each processor. The current proposal minimizes the overall makespan of execution by reasonable levels. Performance of the proposed algorithm is evaluated using DAGs adopted from various state-of-the-art algorithms, real-world problems, like Gaussian elimination (GE) and fast Fourier transformation (FFT) task graph and randomly generated graphs with diverse characteristics. The proposed scheme is compared with four state-of-the-art list-based scheduling algorithms, namely Heterogeneous Earliest Finish Time (HEFT), Predict Earliest Finish Time (PEFT), Heterogeneous Scheduling with Improved task Priority (HSIP), and Task Scheduling for Heterogeneous Computing Systems (TSHCS). Based on the best quality schedule, the obtained results suggest that HLTSD has better results in 87% cases.
收起
摘要 :
A novel task scheduling algorithm called Merge Tasks and Predict Earliest Finish Time (MTPEFT) has been proposed for static task scheduling in a heterogeneous computing environment. The algorithm merges tasks satisfying constraint...
展开
A novel task scheduling algorithm called Merge Tasks and Predict Earliest Finish Time (MTPEFT) has been proposed for static task scheduling in a heterogeneous computing environment. The algorithm merges tasks satisfying constraints and assigns the best processor for the node that has at least one immediate successor as the critical node, thereby effectively reducing the schedule length without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness and frequency of the best result. The results show that the MTPEFT algorithm outperforms the PEFT, CPOP and HEFT algorithms in terms of the schedule length ratio, frequency of the best result and robustness while maintaining the same time complexity.
收起
摘要 :
Recent advancements of virtualization technologies for parallel processing involve scheduling containerized tasks in a workflow. Since a container can include multiple tasks, it can be reused or shared among applications. If every...
展开
Recent advancements of virtualization technologies for parallel processing involve scheduling containerized tasks in a workflow. Since a container can include multiple tasks, it can be reused or shared among applications. If every task in a workflow uses its dedicated container without sharing among any tasks, each container image must be downloaded for each task. As a result, many computational resources are required to process and the communication latency related to container image downloading can become a bottleneck for the makespan. In task scheduling algorithms for workflows, this characteristic produces a new challenging issue that how effectively shares containers among tasks to avoid redundant container image download processes and redundant task allocations. One of the fundamental problems is that no policy has been established for simultaneously satisfying effective container sharing, maintaining the degree of task parallelism, and effective computational resource utilization. In this paper, we propose a clustering-based containerized task scheduling algorithm for clouds, namely, shareable functional task clustering for utilizing virtualized resources (SF-CUV). The objective of SF-CUV is to minimize the makespan with less computational resources and containers than other algorithms by clustering tasks and sharing each container among tasks. SF-CUV consists of two phases: (i)task clustering and pre-virtual CPU (vCPU) allocation phase to derive an accurate scheduling priority, and (ii)task ordering and actual task reallocation phase. Experimental results obtained via simulation and in a real environment show that SF-CUV can utilize both vCPUs and containers with a shorter makespan compared with other approaches.
收起
摘要 :
Tasks scheduling is a key problem in multi-agent system, traditional tasks scheduling methods can't be applied to new application areas of the MAS such as emergency system. In order to apply the Agent method to these new areas, a ...
展开
Tasks scheduling is a key problem in multi-agent system, traditional tasks scheduling methods can't be applied to new application areas of the MAS such as emergency system. In order to apply the Agent method to these new areas, a multi-agent system model is built in this paper, and corresponding task schedulable problem and maximum scheduling problem are defined based on this multi-agent system model. Task schedulable problem is modeled using flow network, and it is proved that maximum flow algorithm can be used to solve such problem, which means the problem can be solved in polynomial time. Furthermore, by analyzing the flow network model, a necessary and sufficient condition which can be used to determine whether tasks can be scheduled is gained and proved. Three approximation algorithms have been proposed to solve the maximum scheduling problem. The experiment results show that all above algorithms can get pretty solutions in solving maximum scheduling problem, and the approximation ratio for optimal solution of these approximation algorithms are all larger than or equal to O.S even though the resource ratio is very low.
收起
摘要 :
Grids involve coordinated resource sharing and problem solving in heterogeneous dynamic environments to meet the needs of a generation of researchers requiring large amounts of bandwidth and more powerful computational resources. ...
展开
Grids involve coordinated resource sharing and problem solving in heterogeneous dynamic environments to meet the needs of a generation of researchers requiring large amounts of bandwidth and more powerful computational resources. The lack of resource ownership by grid schedulers and fluctuations in resource availability require mechanisms which will enable grids to adjust themselves to cope with fluctuations. The lack of a central controller implies a need for self-adaptation. Grids must thus be enabled with the ability to discover, monitor and manage the use of resources so they can operate autonomously. Two different approaches have been conceived to match the resource demands of grid applications to resource availability: Dynamic scheduling and adaptive scheduling. However, these two approaches fail to address at least one of three important issues: (i) the production of feasible schedules in a reasonable amount of time in relation to that required for the execution of an application; (ii) the impact of network link availability on the execution time of an application; and (iii) the necessity of migrating codes to decrease the execution time of an application. To overcome these challenges, this paper proposes a procedure for enabling grid applications, composed of various dependent tasks, to deal with the availability of hosts and links bandwidth. This procedure involves task scheduling, resource monitoring and task migration, with the goal of decreasing the execution time of grid applications. The procedure differs from other approaches in the literature because it constantly considers changes in resource availability, especially network bandwidth availability, to trigger task migration. The proposed procedure is illustrated via simulation using various scenarios involving fluctuation of resource availability. An additional contribution of this paper is the introduction of a set of schedulers offering solutions which differ in terms of both schedule length and computational complexity. The distinguishing aspect of this set of schedulers is the consideration of time requirements in the production of feasible schedules. Performance is then evaluated considering various network topologies and task dependencies.
收起
摘要 :
Abstract In the big data era which we have entered, the development of smart scheduler has become a necessity. A Distributed Stream Processing System (DSPS) has the role of assigning processing tasks to the available resources (dy...
展开
Abstract In the big data era which we have entered, the development of smart scheduler has become a necessity. A Distributed Stream Processing System (DSPS) has the role of assigning processing tasks to the available resources (dynamically or not) and route streaming data between them. Smart and efficient task scheduling can reduce latencies and eliminate network congestions. The most commonly used scheduler is the default Storm scheduler, which has proven to have certain disadvantages, like the inability to handle system changes in a dynamic environment. In such cases, rescheduling is necessary. This paper is an extension of a previous work on dynamic task scheduling. In such a scenario, some type of rescheduling is necessary to have the system working in the most efficient way. In this paper, we extend our previous works Souravlas and Anastasiadou (Appl Sci 10(14):4796, 2020); Souravlas et al. (Appl Sci 11(1):61, 2021) and present a mathematical model that offers better balance and produces fewer communication steps. The scheduler is based on the idea of generating larger sets of communication steps among the system nodes, which we call superclasses. Our experiments have shown that this scheme achieves better balancing and reduces the overall latency.
收起
摘要 :
The rapid development of multi-core systems makes task scheduling in multi-core systems a new research topic. While tasks are running in parallel, how to improve the efficiency of the system and maintain the load balance of the sy...
展开
The rapid development of multi-core systems makes task scheduling in multi-core systems a new research topic. While tasks are running in parallel, how to improve the efficiency of the system and maintain the load balance of the system is the focus of research in the new era. Aiming at the problem that the multi-core scheduling algorithm based on task duplication does not consider the load balance of each CPU, which leads to the problem of reduced CPU utilization. This paper combines a hierarchical idea on the basis of task replication, and proposes a new hierarchical multi-core scheduling algorithm TDLS algorithm based on task replication. This algorithm is based on the idea of hierarchical scheduling. According to the fact that there is no dependency relationship between tasks at the same layer after layering, the task scheduling sequence is adjusted to reduce the waste on the core, shorten the waste between cores caused by communication time, and reduce the number of processors. , Thereby greatly improving the CPU utilization rate, using the least time and the least number of cores to complete scheduling, making the load of multi-core scheduling more balanced. Experiments show that under the same experimental conditions, compared with the traditional multi-core scheduling algorithm based on task replication, the improved algorithm TDLS reduces the number of processor cores, and also shortens the scheduling length of the total task. Its performance is better than the traditional multi-core scheduling algorithm based on task replication.
收起
摘要 :
Task schedule optimization enables to attain high performance in both homogeneous and heterogeneous computing environments. The primary objective of task scheduling is to minimize the execution time of an application graph. Howeve...
展开
Task schedule optimization enables to attain high performance in both homogeneous and heterogeneous computing environments. The primary objective of task scheduling is to minimize the execution time of an application graph. However, this is an NP-complete (non-deterministic polynomial) undertaking. Additionally, task scheduling is a challenging problem due to the heterogeneity in the modern computing systems in terms of both computation and communication costs. An application can be considered as a task graph represented using Directed Acyclic Graphs (DAG). Due to the heterogeneous system, each task has different execution time on different processors. The primary concern in this problem domain is to reduce the schedule length with minimum complexity of the scheduling procedure. This work presents a couple of hybrid heuristics, based on a list and guided random search to address this concern. The proposed heuristic, i.e., Hybrid Heuristic and Genetic-based Task Scheduling Algorithm for Heterogeneous Computing (HHG) uses Genetic Algorithm and a list-based approach. This work also presents another heuristic, namely, Hybrid Task Duplication, and Genetic-based Task Scheduling Algorithm for Heterogeneous Computing (HTDG). The present work improves the quality of initial GA population by inducing two diverse guided chromosomes. The proposal is compared with four state-of-the-art methods, including two evolutionary algorithms for the same task, i.e., New Genetic Algorithm (NGA) and Enhanced Genetic Algorithm for Task Scheduling (EGA-TS), and two list-based algorithms, i.e., Heterogeneous Earliest Finish Time (HEFT), and Predict Earliest Finish Time (PEFT). Results show that the proposed solution performs better than its counterparts based on occurrences of the best result, average makespan, average schedule length ratio, average speedup, and the average running time. HTDG yields 89% better results and HHG demonstrates 56% better results in comparisons to the four state-of-the-art task scheduling algorithms.
收起
摘要 :
The results of simulation studies designed to assess two of the fitness functions (Or1 and Or2) for the GRASP algorithm used in the elastic scheduling task model (ESTM) have been presented in the paper. The obtained results indica...
展开
The results of simulation studies designed to assess two of the fitness functions (Or1 and Or2) for the GRASP algorithm used in the elastic scheduling task model (ESTM) have been presented in the paper. The obtained results indicate that the GRASP algorithm with the fitness function Or2 was better at choosing new settings for T_(sel) to exploit the hardware resources of a mobile robot. Furthermore, it has been found that for Or2 new settings for T_(sel) are closer to T_(nom) than T_(max) (task cycle execution is reduced which enables a quicker response of a mobile robot to events).
收起
摘要 :
Shift Minimization Personnel Task Scheduling Problem (SMPTSP) is assigning a given set of predetermined tasks (with known start and finish times) to a minimum number of heterogeneous workers with predetermined shifts. Each task ca...
展开
Shift Minimization Personnel Task Scheduling Problem (SMPTSP) is assigning a given set of predetermined tasks (with known start and finish times) to a minimum number of heterogeneous workers with predetermined shifts. Each task can be performed only by a specific subset of workers. Every task must be assigned to a worker. A worker cannot perform more than one task at a time, and tasks cannot be preempted. SMPTSP is NP-hard, but there is practical interest in solving very large instances of it in ground crew scheduling of a large airline in a large airport. Recently, there have been a few papers reporting various solution methods for large instances of SMPTSP. However, solving very large instances of SMPTSP remains a challenge. In this paper, we propose a novel greedy heuristic solution method for SMPTSP. A reduced problem is solved iteratively by selecting the best possible assignment of tasks to one worker. We have tested the Greedy heuristic method on 3 sets of available large test problems. The results show that the heuristic method performs well relative to the current solution methods, and has the added advantage of being able to solve very large instances fast. (C) 2018 Elsevier Ltd. All rights reserved.
收起
原文获取